/**
 * 
 */
package combinatorics.passed;

/**
 * @author Michael
 * The set [1,2,3,�,n] contains a total of n! unique permutations.
 * By listing and labeling all of the permutations in order,
 * We get the following sequence (ie, for n = 3):
 * "123"
 * "132"
 * "213"
 * "231"
 * "312"
 * "321"
 * Given n and k, return the kth permutation sequence.
 * Note: Given n will be between 1 and 9 inclusive.
 */
public class PermutationSequence {

	public String getPermutation(int n, int k) {
		assert (n >= 1);
		assert (k > 0);
		// generate stirng for n
		char[] s = new char[n];
		for (int i = 0; i < n; ++i) {
			s[i] = (char) ('0' + i + 1);
		}

		for (int i = 1; i < k; ++i) {
			NextPermutation.nextPermutation(s);
		}

		return new String(s);
	}

	public String getPermutationRecursive(int n, int k) {
		assert (n >= 1);
		assert (k > 0);
		// generate stirng for n
		char[] s = new char[n];
		for (int i = 0; i < n; ++i) {
			s[i] = (char) ('0' + i + 1);
		}

		for (int i = 1; i < k; ++i) {
			NextPermutation.nextPermutation(s);
		}

		return new String(s);
	}

	int count;
	StringBuffer result = new StringBuffer();

	public String getPermutation1(int n, int k) {
		count = 0;
		if (n == 0 || k == 0) {
			return "";
		}

		StringBuffer sol = new StringBuffer();
		StringBuffer result = new StringBuffer();
		permute(n, k, 1, sol, result);
		//  System.out.println("pass is:" + result);
		String ret = new String(result);
		return ret;
	}

	public void permute(int n, int k, int level, StringBuffer sol,
			StringBuffer result) {
		if (level == n + 1) {
			count++;
			//System.out.println(sol);
			if (count == k) {
				result.append(sol);
			}
			//System.out.println("safe result as: " + result);
		}

		for (int i = level; i <= n; i++) {
			sol.append(i);
			permute(n, k, level + 1, sol, result);
			sol.setLength(sol.length() - 1);
		}

	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		PermutationSequence ps = new PermutationSequence();
		for (int i = 1; i <= 6; i++)
			System.out.println(ps.getPermutation1(3, i));
	}

	/**
	 * 
	 */
	public PermutationSequence() {
		// TODO Auto-generated constructor stub
	}
}
